package com.cango.student.algorithm.sort;

import java.util.Arrays;

public class QuickS {

    public static void quickS(int[] arr, int left,int right) {
        if (left > right) return;

        int i = left, j = left;
        int tmp = arr[right];

        while (j < right) {
            if (arr[j] < tmp) {
                if (i != j) {
                    int t = arr[j];
                    arr[j] = arr[i];
                    arr[i] = t;
                }

                ++i;
            }

            j++;
        }

        arr[right] = arr[i];
        arr[i]=tmp;
        quickS(arr, left, i-1);
        quickS(arr, i+1,right);
    }

    public static void main(String[] args) {
        int[] arr = {10,9,18,2,48,69,66};
        quickS(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);

    }
}
